package nl.rug.jvleusen.datastructurelib.set;

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import nl.rug.jvleusen.datastructurelib.ISet;

/**
 * This is a default LinkedList implementation, this is a growing data structure
 * that can be added to indefinitely (as much as memory allows).
 *
 * @author Jeroen van Leusen
 */
public class LinkedList<E> implements ISet<E> {

    private ListNode<E> header = new ListNode<E>(null);
    private ListNode<E> lastNode = header;
    private int size = 0;

    /**
     * This is here so you can create a LinkedList without a prior Collection,
     * does not actually do anything.
     */
    public LinkedList() {
        //No setup required.
    }

    /**
     * Initializes linkedlist by inserting all elements of the specified
     * collection
     *
     * @param c Collection to add to this linked list.
     */
    public LinkedList(Collection<? extends E> c) {
        addAll(c);
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> union(ISet<E> set2) {
        LinkedList<E> result = new LinkedList(this);
        result.addAll(set2);
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> intersection(ISet<E> set2) {
        LinkedList<E> result = new LinkedList(this);
        result.retainAll(set2);
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public ISet<E> difference(ISet<E> set2) {
        LinkedList<E> result = (LinkedList<E>) union(set2);
        result.removeAll(intersection(set2));
        return result;
    }

    /**
     * {@inheritDoc}
     */
    public boolean subset(ISet<E> set2) {
        LinkedList<E> intersection = (LinkedList<E>) intersection(set2);
        //Intersection should contain all elements of set2.
        return intersection.containsAll(set2);
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size() == 0;
    }

    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    public Iterator<E> iterator() {
        return new Iterator<E>() {

            ListNode<E> next = header.next;
            ListNode<E> lastReturned = header;

            public boolean hasNext() {
                return next != null;
            }

            public E next() {
                if (next == null) {
                    throw new NoSuchElementException();
                }
                lastReturned = next;
                next = next.next;
                return lastReturned.data;
            }

            public void remove() {
                ListNode<E> lastNext = lastReturned.next;
                try {
                    LinkedList.this.remove(lastReturned);
                } catch (NoSuchElementException e) {
                    //Someone really has been messing with this list.
                    throw new IllegalStateException();
                }

                lastReturned = header;
            }
        };
    }

    public Object[] toArray() {
        Object[] result = new Object[size()];
        int i = 0;
        for (ListNode<E> ln = header.next; ln != null; ln = ln.next) {
            result[i++] = ln.data;
        }
        return result;
    }

    public <T> T[] toArray(T[] a) {
        //Create a new array with reflection is the array provided is too small
        if (a.length < size()) {
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size());
        }
        int i = 0;

        Object[] result = a; //This will make sure elements can throw a ArrayStoreException.
        for (ListNode<E> ln = header.next; ln != null; ln = ln.next) {
            result[i++] = ln.data;
        }

        return a;
    }

    public boolean add(E e) {
        if (contains(e)) {
            return false;
        }

        ListNode<E> newNode = new ListNode(e);

        this.lastNode.next = newNode;
        this.lastNode = newNode;
        size++;

        return true;
    }

    public boolean remove(Object o) {
        //Split null off to avoid NPE's
        if (o == null) {
            for (ListNode<E> ln = header.next; ln != null; ln = ln.next) {
                if (ln.data == null) {
                    remove(ln);
                    return true;
                }
            }
        } else {
            for (ListNode<E> ln = header.next; ln != null; ln = ln.next) {
                if (o.equals(ln.data)) {
                    remove(ln);
                    return true;
                }
            }
        }
        return false;
    }

    private E remove(ListNode<E> listNode) {
        //Removing the header would be BAD.
        if (listNode == header) {
            throw new NoSuchElementException();
        }

        E result = listNode.data;
        //We need to find the one before this one!
        ListNode<E> previousNode = header;

        while (previousNode != null && previousNode.next != listNode) {
            previousNode = previousNode.next;
        }

        previousNode.next = listNode.next;

        listNode.next = null;
        listNode.data = null;
        size--;

        return result;

    }

    public boolean containsAll(Collection<?> c) {
        for (Object element : c) {
            if (!contains(element)) {
                //Its not contained within this list, return false;
                return false;
            }
        }
        return true;
    }

    public boolean addAll(Collection<? extends E> c) {
        boolean changed = false;
        for (E element : c) {
            if (add(element)) {
                //It was successfully added.
                changed = true;
            }
        }
        return changed;
    }

    public boolean removeAll(Collection<?> c) {
        boolean changed = false;

        //We need iterator.remove(), so we dont use the for (element:collection) method.
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (c.contains(it.next())) {
                //Element contained in c, remove!
                it.remove();
                //We've changed the list!
                changed = true;
            }
        }

        return changed;
    }

    public boolean retainAll(Collection<?> c) {
        boolean changed = false;

        //We need iterator.remove(), so we dont use the for (element:collection) method.
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            if (!c.contains(it.next())) {
                //Element not contained in c, remove!
                it.remove();
                //We've changed the list!
                changed = true;
            }
        }

        return changed;
    }

    public void clear() {
        ListNode<E> ln = header.next;
        //Prevent memory leaks by setting all references to null.
        while (ln != null) {
            ListNode<E> next = ln.next;
            ln.next = null;
            ln.data = null;
            ln = next;
        }
        //Reset header and size.
        header.next = null;
        lastNode = header;
        size = 0;
    }

    private int indexOf(Object o) {
        int index = 0;

        //Avoid NPE's!
        if (o == null) {
            for (ListNode ln = header.next; ln != null; ln = ln.next) {
                if (ln.data == null) {
                    return index;
                }
                index++;
            }
        } else {
            for (ListNode ln = header.next; ln != null; ln = ln.next) {
                if (o.equals(ln.data)) {
                    return index;
                }
                index++;
            }
        }

        return -1;
    }

    private static class ListNode<E> {

        private E data;
        private ListNode<E> next;

        protected ListNode(E data) {
            this(data, null);
        }

        protected ListNode(E data, ListNode<E> next) {
            this.data = data;
            this.next = next;
        }
    }
}
